package model

type LRUCache struct {
	Head, Tail *Node
	Keys       map[int]*Node
	Cap        int
}

type Node struct {
	Key, Val  int
	Pre, Next *Node
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		Keys: make(map[int]*Node),
		Cap:  capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	node, ok := this.Keys[key]
	if !ok {
		return -1
	}
	this.Remove(node)
	this.Add(node)
	return node.Val
}

func (this *LRUCache) Put(key int, value int) {
	node, ok := this.Keys[key]
	if ok {
		node.Val = value
		this.Remove(node)
		this.Add(node)
		return
	} else {
		node = &Node{Key: key, Val: value}
		this.Keys[key] = node
		this.Add(node)
	}

	if this.Cap < len(this.Keys) {
		delete(this.Keys, this.Tail.Key)
		this.Remove(this.Tail)
	}
}

func (this *LRUCache) Add(node *Node) {
	node.Pre = nil
	node.Next = this.Head
	if this.Head != nil {
		this.Head.Pre = node
	}
	this.Head = node
	if this.Tail == nil {
		this.Tail = node
		this.Tail.Next = nil
	}
}

func (this *LRUCache) Remove(node *Node) {
	if node == this.Head {
		this.Head = node.Next
		node.Next = nil
		return
	}

	if node == this.Tail {
		this.Tail = node.Pre
		node.Pre.Next = nil
		node.Pre = nil
		return
	}
	node.Pre.Next = node.Next
	node.Next.Pre = node.Pre
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
